這是什麼？

一言以敝之，字典樹，屬於 Tree 的衍生資料結構。
結構上一樣有 root，視為起點，第一層為各個單字的第一個字母，接著依照單字的字母，依序填入。

第一層到任意 Leaf，都可以成為一個單字。

刷題：208. Implement Trie (Prefix Tree)

題目

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

思考

沒錯，LeetCode 有一題專門要求答題者實作 Trie，三個方法皆是 Trie 會使用到的基本方法。

解題

JS

/**
 * Initialize your data structure here.
 */
var TrieNode = function (key) {
  return {
    key: key,
    isWord: false
  };
};

var Trie = function () {
  this.trie = {};
};

/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  let trie = this.trie;

  for (let i = 0; i < word.length; i++) {
    const char = word[i];

    if (!trie[char]) {
      trie[char] = {};
    }

    trie = trie[char];
  }

  trie.isEnd = true;
};

/**
 * Returns if the word is in the trie.
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  let currentNode = this.trie;

  for (let i = 0; i < word.length; i++) {
    const char = word[i];

    if (currentNode[char] === undefined) {
      return false;
    }

    currentNode = currentNode[char];
  }

  return currentNode.isEnd === true;
};

/**
 * Returns if there is any word in the trie that starts with the given prefix.
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  let currentNode = this.trie;

  for (let i = 0; i < prefix.length; i++) {
    const char = prefix[i];

    if (currentNode[char] === undefined) {
      return false;
    }

    currentNode = currentNode[char];
  }

  return true;
};

Java

class Trie {
    private Node root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new Node(false);
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);

            if (!node.children.containsKey(ch)) {
                node.children.put(ch, new Node(false));
            }

            node = node.children.get(ch);
            node.endOfWord |= (i == word.length() - 1);
        }
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            node = node.children.get(ch);
            if (null == node)
                return false;
        }
        return node.endOfWord;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        Node node = root;
        for (int i = 0; i < prefix.length(); ++i) {
            char ch = prefix.charAt(i);
            node = node.children.get(ch);
            if (null == node)
                return false;
        }
        return true;
    }

    static class Node {
        private Map<Character, Node> children;
        private boolean endOfWord;

        public Node(boolean endOfWord) {
            this.endOfWord = endOfWord;
            this.children = new HashMap<>();
        }
    }
}

C

#define ALPHABET_SIZE (26)

typedef struct
{
    struct Trie *children[ALPHABET_SIZE];
    bool isLeaf;
} Trie;

/** Initialize your data structure here. */

Trie *trieCreate()
{
    Trie *newNode = malloc(sizeof(Trie));

    int i;
    for (i = 0; i < ALPHABET_SIZE; i++)
    {
        newNode->children[i] = NULL;
    }

    newNode->isLeaf = false;
    return newNode;
}

/** Inserts a word into the trie. */
void trieInsert(Trie *obj, char *word)
{
    int index;
    int length = strlen(word);
    int i;

    for (i = 0; i < length; i++)
    {
        index = word[i] - 'a';

        if (!obj->children[index])
        {
            obj->children[index] = trieCreate();
        }

        obj = obj->children[index];
    }

    obj->isLeaf = true;
}

/** Returns if the word is in the trie. */
bool trieSearch(Trie *obj, char *word)
{
    int index;

    for (int i = 0; i < strlen(word); i++)
    {
        index = word[i] - 'a';
        if (!obj->children[index])
        {
            return false;
        }

        obj = obj->children[index];
    }

    return (obj != NULL && obj->isLeaf);
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool trieStartsWith(Trie *obj, char *prefix)
{
    int index;
    int length = strlen(prefix);
    int i;

    for (i = 0; i < length; i++)
    {
        index = prefix[i] - 'a';

        if (!obj->children[index])
        {
            return false;
        }

        obj = obj->children[index];
    }

    return true;
}

void trieFree(Trie *obj)
{
    free(obj);
}

看法

實作上有幾點要注意：

• 要製作節點。
• insert 的做法：
  • 將插入的單字拆解成一個一個的字元
  • 從第一個字元開始，檢查 Trie 物件有沒有這個字元的屬性
    • 有，沒事。
    • 沒有，新增該節點。
  • 重複上述行為，直到該單字插入完成。
• search 的做法：
  • 將搜尋的單字拆解成一個一個的字元
    • 從第一個字元開始，檢查 Trie 物件有沒有這個字元的屬性
    • 有，繼續下個字元。
    • 沒有，回傳 false。
    • 判斷該節點是否有 isEndOfWord，同時確認是否檢查完所有字元。
  • 重複上述行為，直到所有字元檢查完成。
• startsWith 與 search 類似，差別在：
  • 不用檢查 isEndOfWord

結論

Trie 可以當成是專門儲存 Strings 的可行方案，尤其需要 prefix search 的情況特別適合。